洛谷 P1131 [ZJOI2007]时态同步 题解

发表于 | 分类于 | | 热度: ℃

Description

一块电路板由若干个节点组成，用数字 $1,2,3…$ 进行标号。各个节点由若干不相交的导线连接。对于任何两个节点，存在且仅存在一条通路。第 $e$ 条边通过的时间为 $t_e$。

电路板上存在一个“激发器”，产生激励电流。中间节点对电流沿边进行转发。接受电流不再转发的节点称为 终止节点。所有终止节点接受电流的时间 全部相同 时，称为达到 时态同步 。

小 $Q$ 有一个道具，每次可以使任意边的通过时间 $+1$。求达到时态同步使用道具的最少次数。

数据范围：$n<=500000, t_e<=1000000$

Solution

读入 $n$ 个点，$n-1$ 条边。可知是以激发器为根节点的一棵树。其终止节点为叶节点。从叶子节点开始，对于每一个节点 $i$，使其儿子到它的时间全部相同，累计答案。

可以在 $dfs$ 回溯的时候处理。时间复杂度为 $O(n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;

const int N = 2333333;
struct edge
{
    int nxt, to, w;
} e[N];
int n, s, a, b, c, cnt = 0, sum = 0, ans = 0, head[N], f[N];

void add(int x, int y, int w)
{
    e[++cnt] = (edge) { head[x], y, w};
    head[x] = cnt;
}

void dfs(int x, int fa)
{
    for(int i = head[x]; i; i = e[i].nxt)
        if(e[i].to != fa) dfs(e[i].to, x);
    for(int i = head[x]; i; i = e[i].nxt)
        if(e[i].to != fa) f[x] = max(f[x], e[i].w);
    for(int i = head[x]; i; i = e[i].nxt)
        if(e[i].to != fa) ans += f[x] - e[i].w;
    for(int i = head[fa]; i; i = e[i].nxt)
        if(e[i].to == x) e[i].w += f[x];
}

signed main()
{
    scanf("%lld%lld", &n, &s);
    for(int i = 1; i < n; i++)
    {
        scanf("%lld%lld%lld", &a, &b, &c);
        add(a, b, c); add(b, a, c);
    }
    memset(f, 0, sizeof(f));
    dfs(s, 0);
    printf("%lld", ans);
    return 0;
}